package stool.sort;

import static stool.sort.resource.ResourceClass.*;

/**
 * @author Felix
 * @Description 快速排序
 * @Date 2022-07-02
 */
public class QuickSort {

    public static void main(String[] args) {

        int[] arr = findIntArr();
        quickSort(arr, 0, arr.length - 1);
        print(arr);
    }

    /**
     * 快速排序就是按照基准点排序，从基准点右侧找小于基准点的，从基准点左边找大于基准点的，交换两数，直至重合后与基准点交换，此时基准点位置正确，排序基准点左侧，然后排序基准点右侧
     * @param arr 排序数组
     * @param left 排序起始位置，即基准数
     * @param right 排序终点位置
     */
    public static  void quickSort(int[] arr, int left, int right) {
        if (left > right) {
            return;
        }

        // 基准数
        int base = arr[left];
        // 指向左边
        int i = left;
        // 指向右边
        int j = right;

        // 指针不相遇
        while (i != j) {
            // 从右边，有比基准数小的就停下来，大就继续
            while (arr[j] >= base && i < j) {
                j--;
            }
            // 从左边，有比基准数大停下来，小就继续
            while (arr[i] <= base && i < j) {
                i ++;
            }
            // 交换i和j
            swap(arr, i, j);
        }

        // 指针相遇,基准数放在相遇位置
        arr[left] = arr[i];
        arr[i] = base;

        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }
}
